mod route {
    use petgraph::algo::{all_simple_paths, astar, dijkstra};
    use petgraph::graph::DefaultIx;
    use petgraph::graph::{Graph, DiGraph, UnGraph, NodeIndex};
    use petgraph::visit::EdgeRef;
    use petgraph::Direction;
    use std::collections::HashMap;

    pub fn shortest_path() {
        let mut graph = DiGraph::new();

        // 添加节点
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        let c = graph.add_node("C");
        let d = graph.add_node("D");

        // 添加边及权重
        graph.add_edge(a, b, 1);
        graph.add_edge(b, c, 2);
        graph.add_edge(c, d, 1);
        graph.add_edge(a, d, 4);

        // 寻找从A到D的最短路径
        let result = dijkstra(&graph, a, Some(d), |e| *e.weight());

        println!("{:?}", result);

        // 打印路径
        let mut path = vec![d.index()];
        let mut cur_node = d;

        while cur_node != a {
            let m = graph
                .edges_directed(cur_node, Direction::Incoming)
                .map(|edge| result.get(&edge.source()).unwrap())
                .min()
                .unwrap();
            let v = *m as usize;
            path.push(v);
            cur_node = NodeIndex::new(v);
        }

        let mut path_node = vec![];
        for i in path.iter().rev().map(|v| graph[NodeIndex::new(*v)]) {
            path_node.push(i);
        }
        println!("Dijkstra algorithm: {:?}", path_node);

        let path = astar(&graph, a, |n| n == d, |e| *e.weight(), |_| 0);
        println!("Astar algorithm: {:?}", path)
    }

    pub fn all_simple_path() {
        let mut digraph = DiGraph::<_, i32>::new();

        let a = digraph.add_node("A");
        let b = digraph.add_node("B");
        let c = digraph.add_node("C");
        let d = digraph.add_node("D");

        digraph.extend_with_edges(&[
            (a, b, 1),
            (b, a, 1),
            (a, c, 1), 
            (c, a, 1),
            (b, c, 1), 
            (c, b, 1),
            (c, d, 1), 
            (d, c, 1),
            (b, d, 1),
            (d, b, 1)
            ]);

        let ways = all_simple_paths::<Vec<_>, _>(&digraph, a, d, 0, None)
            .map(|way | way.into_iter().map(|n| digraph[n].to_string()).collect::<Vec<_>>())
            .collect::<Vec<_>>();
        println!("All simple paths: {:?}", ways);


        let mut graph = UnGraph::<_, i32>::new_undirected();
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        let c = graph.add_node("C");
        let d = graph.add_node("D");
        
        graph.extend_with_edges(
            &[
                (a, b, 1),
                (a, c, 1),
                (c, b, 1),
                (c, d, 1),
                (b, d, 1),
            ]
        );
        let ways = all_simple_paths::<Vec<_>, _>(&graph, a, d, 0, None)
            .map(|way | way.into_iter().map(|n| digraph[n].to_string()).collect::<Vec<_>>())
            .collect::<Vec<_>>();
        println!("All simple paths: {:?}", ways);
        
        // 打印graph所有的边
        for edge in graph.edge_references() {
            println!("{:?} -> {:?} with weight {}", edge.source(), edge.target(), edge.weight());
        }



    }
    
}

fn main() {
    use crate::route::*;

    shortest_path();
    all_simple_path();
}
